#include <bits/stdc++.h>

using namespace std;
class LFUCache
{
private:
    struct Node
    {
        int key, value, time = 0, count = 0;
        bool operator<(const Node &rhs) const
        {
            return count == rhs.count ? time < rhs.time : count < rhs.count;
        }
    };
    unordered_map<int, Node> m_; // key-;
    set<Node> s_;                // count-value;
    int capacity_;
    int time_;

public:
    LFUCache(int capacity)
        : capacity_(capacity)
    {
        time_ = 0;
    }

    int get(int key)
    {
        if (capacity_ == 0)
        {
            return -1;
        }
        if (m_.find(key) == m_.end())
        {
            return -1;
        }
        s_.erase(m_[key]);
        m_[key].count++;
        m_[key].time = ++time_;
        s_.insert(m_[key]);
        return m_[key].value;
    }

    void put(int key, int value)
    {
        if (m_.find(key) == m_.end())
        {
            Node newNode{key, value, ++time_, 1};
            if (m_.size() == capacity_)
            {
                auto it = s_.begin();
                m_.erase(it->key);
                s_.erase(it);
            }

            m_.insert({key, newNode});
            s_.insert(newNode);
        }
        else
        {
            s_.erase(m_[key]);
            m_[key].value = value;
            m_[key].count++;
            m_[key].time = ++time_;
            s_.insert(m_[key]);
        }
    }
};